package com.bascker.algorithm.practice.arr.easy.third_max;

import java.util.Comparator;
import java.util.Objects;
import java.util.TreeSet;

/**
 * 第三大的数: 给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。
 * 要求算法时间复杂度必须是O(n)。
 *
 * For example:
 *   in: [3, 2, 1]      out: 1
 *   in: [1, 2]         out: 2
 *   in: [2, 2, 3, 1]   out: 1
 *
 * @author bascker
 * @apiNote leetcode T414
 */
public class Solution {

    // 选择一种好的数据结构，对解题很有帮助 。因为题目限制时间复杂度必须为 O(n)，因此我们无法对原数组进行预排序
    // 选择利用树型结构来处理，维持一个只有 3 个结点的数，并在插入节点时进行自然序排序，其时间复杂度为 nlogn.
    // 节点数为 3，因此在维持这棵树的时间上，复杂度为 3lon3 = O(1)。加上一趟线性扫描的时间，总体时间复杂度就是 O(n)，满足要求
    public int thirdMax(int[] nums) {
        if (Objects.isNull(nums)) {
            return 0;
        }

        // 数据结构的运用
        // 1. 利用 TreeSet 维持自然序(降序)，进行 3 个最大值的寻找 => 类似最大堆 topK 的解法，但是堆需要手动去重
        // 2. 利用 Set 进行去重，保持最大值的唯一性
        final Comparator<Integer> desc = (a, b) -> a > b ? -1 : a.equals(b) ? 0 : 1;
        TreeSet<Integer> treeSet = new TreeSet<>(desc);

        for (int x : nums) {
            treeSet.add(x);
            if (treeSet.size() > 3) {
                // 移除最小值
                treeSet.remove(treeSet.last());
            }
        }

        return treeSet.size() == 3 ? treeSet.last() : treeSet.first();
    }

}
